package imooc_math;

import java.util.LinkedList;
import java.util.Queue;

public class BST<Key extends Comparable,Value> {
	private int count;
	private Node root;
	private BST bst;
	private class Node{
		Key key;
		Value value;
		Node left,right;
		public Node(Key key,Value value){
			this.key=key;
			this.value=value;
			left=right=null;
		}
	}
	public BST(){
		root=null;
		count=0;
	}
	public boolean isEmpty(){
		return count==0;
	}
	public void insert(Key key,Value value){
		root=insert(root,key,value);
	}
	public  Node insert(Node node,Key key,Value value){
		if(node==null){
			return bst.new Node(key,value);
		}else if(key.compareTo(node.key) == 0){
			node.value=value;
		}else if(key.compareTo(node.key) < 0){
			node.left=insert(node.left,key,value);
		}else{//key.compareTo(node.key) > 0
			node.right=insert(node.right,key,value);
		}
		return node;
	}
	public boolean contain(Key key){
		return contain(root,key);
	}
	public boolean contain(Node node,Key key){
		if(node==null){
			return false;
		}else if(key.compareTo(node.key)==0){
			return true;
		}else if(key.compareTo(node.key)<0){
			return contain(node.left,key);
		}else{//key.compareTo(node.key)>0
			return contain(node.right,key);
		}
	}
	/*search方法有多种实现：
	 * 1.返回Node对象：如果查找不到，返回null;如果查找到了，返回查找到的Node对象
	 * 	   缺点：内部的Node对象是封装的，如果使用这种方式，必须把Node类写成public的，
	 * 	   并且使用者还必须了解Node的实现，这是不必要的。
	 * 2.返回value的值：
	 * 	 问题：如果查找不到，要表示并不容易。（比如在数组中的查找，找到就返回数组下标，找不到返回-1，这就是查找不到的表示）
	 * 3.返回Value对象：如果查找不到，返回null;找到的话返回Value对象。
	 */
	public Value search(Key key){
		search(root,key);
		return null;
	}
	public Value search(Node node,Key key){
		if(node==null){
			return null;
		}else if(key.compareTo(node.key)==0){
			return node.value;
		}else if(key.compareTo(node.key)<0){
			return search(node.left,key);
		}else{//key.compareTo(node.key)>0
			return search(node.right,key);
		}				
	}
	public void proOrder(){
		proOrder(root);
	}
	public void proOrder(Node node){
		if(node != null){
			System.out.println(node.key);
			proOrder(node.left);
			proOrder(node.right);
		}
		
	}
	public void inOrder(){
		inOrder(root);
	}
	public void inOrder(Node node){
		if(node != null){
			inOrder(node.left);
			System.out.println(node.key);
			inOrder(node.right);
		}
		
	}
	public void postOrder(){
		postOrder(root);
	}
	public void postOrder(Node node){
		if(node != null){
			postOrder(node.left);
			postOrder(node.right);
			System.out.println(node.key);
		}
		
	}
	public void levelOrder(){
		Queue<Node> q=new LinkedList<Node>();//数据结构：队列
		q.add(root);
		while(!q.isEmpty()){
			Node node=q.remove();
			System.out.println(node.key);
			if(node.left!=null){
				q.add(node.left);
			}
			if(node.right!=null){
				q.add(node.right);
			}
		}
		
	}
	//找到最小值
	public Node miniNum(){
		if(count != 0){
			Node minNum = miniNum(root);
			return minNum;
		}else{//count == 0
			return null;
		}
	}
	public Node maxNum(){
		if(count != 0){
		Node maxNum = maxNum(root);
		return maxNum;
		}else{
			return null;			
		}
	}
	public Node miniNum(Node node){
		if(node.left == null){
			return node;
		}
		return miniNum(node.left);//递归
	}
	public Node maxNum(Node node){
		if(node.right == null){
			return node;
		}
		return maxNum(node.right);
	}
	public Node mininum1(Node node){
		while(node.left != null){
			node = node.left; 
		}
		return node;
	}
	public void removeMin(){
		if(root !=null){
			root = removeMin(root);
		}	
	}
	public Node removeMin(Node node){
		if(node.left == null){
			/*if(node.right != null){
				node = node.right;
			}else{
				node = null;
			}*/
			count --;
			return node.right;
		}else{
			node.left = removeMin(node.left);
		}
		return  node;
	}
	public void removeMax(){
		if(root !=null){
			root = removeMax(root);
		}
	}
	/*删除掉以node为跟的二分搜索树中的最大节点
	 * 并返回删除节点后新的二分搜索树的跟*/
	public Node removeMax(Node node){
		if(node.right == null){//node已经是最大了
			/*node.left != null : node = node.left ;
			  node.left == null : node = null;
			 */		
			return node.left;
		}
		node.right = removeMax(node.right);
		return node;
	}
	//review
	public Node remove(Node node,Key key){
		if(node == null){
			return null;
		}
		if(key.compareTo(node.key) < 0){
			node.left = remove(node.left,key);
			return node;
		}else if(key.compareTo(node.key) > 0){
			node.right = remove(node.right,key); 
			return node;
		}else{// node.key.compareTo(key) == 0
			if(node.left == null){
				return node.right;
			}
			if(node.right == null){
				return node.left;
			}
			//node.left!=null&node.right!=null
			Node successor = miniNum(node.right);
			successor.left = node.left;
			successor.right = removeMin(node.right);
			count--;
			
			return successor;
		}
		
	}
	/*自己的实现(错误)
	public void removeMax(Node node){
		if(node.right == null){
			//正确做法：当找到最大值(node.right == null)之后，需要刷新上层节点的right值
			node = node.left;//思路错误：只是改变了形参node指向的地址
		}else{
			removeMax(node.right);
		}
	}*/	
}
